/**
* 目前的文法模型，从文法层面实现操作符的优先级
*  0 <program> ::= <function>
   1 <function> ::= <data_type> <id> "(" ")" "{" <statement> "}"
   2 <statement> ::= "return" <exp> ";"
   3 <exp> ::= <term>
   4 <exp> ::= <exp> ("+" | "-") <term>
   5 <term> ::= <factor>
   6 <term> ::= <term> ("*" | "/") <factor>
   7 <factor> ::= <int>
   8 <factor> ::= <unary_op> <factor>
   9 <factor> ::= "(" <exp> ")"

* 优先级低的先计算的话，按如下优先级标准计算
* "()" "[]" 的优先级为 1
* <unary_op> 的优先级为 2
* "*","/" 的优先级为 3
* "+","-" 的优先级为 4
*
* dfa 构建 参见 dfa_draft.md
*/
use crate::{
    lexer::{BraceType, OpType, Token, keyword::is_data_type},
    parser::{pd::PD, production::get_production},
};

#[derive(Debug)]
pub struct DFAOutput {
    pub action: Action,
}

// 错误类型
#[derive(Debug, Clone, PartialEq)]
pub enum DFAError {
    NoAction,
    NoState,
    NoProduction,
    NoGoto,
    ASTNotAccepted,
    ASTRootNoSymbol,
    StackNoSymbol,
    StackEmpty,
    UnknownToken,
}

#[derive(Debug)]
pub struct DFA {
    state: u32,
    sta: Vec<(Option<ASTLink>, u32)>,
    is_ac: bool,
}

impl DFA {
    pub fn new() -> Self {
        DFA {
            state: 0,
            sta: vec![(None, 0u32)],
            is_ac: false,
        }
    }

    pub fn reset(&mut self) {
        self.state = 0;
        self.sta = vec![(None, 0u32)];
        self.is_ac = false;
    }

    pub fn is_accepted(&self) -> bool {
        self.is_ac
    }

    pub fn ast_clone(&self) -> Result<ASTLink, DFAError> {
        if !self.is_accepted() {
            return Err(DFAError::ASTNotAccepted);
        }

        match &self.sta.last().unwrap().0 {
            Some(r) => Ok(r.clone()),
            None => Err(DFAError::ASTRootNoSymbol),
        }
    }

    pub fn step(&mut self, t: &Token, idx: usize) -> Result<DFAOutput, DFAError> {
        //println!("Step on state {}.", self.state);

        match get_action(&self.state, &t) {
            Ok(action) => match action {
                Action::Shift(s) => {
                    self.state = s;
                    self.sta.push((
                        Some(ASTLink {
                            sym: Symbol::Term(t.clone()),
                            adj: vec![],
                            index: idx,
                            prod_id: None,
                            pd: None,
                            parser_ok: false,
                        }),
                        s,
                    ));

                    Ok(DFAOutput { action: action })
                }
                Action::Reduce(p) => {
                    let mut reduced: Vec<ASTLink> = vec![];
                    //let mut reduced_sym : Vec<Symbol> = vec![];

                    let prod = get_production(&p)?;
                    let mut n = prod.n_rhs;

                    // Pop from stack
                    while n != 0 {
                        n -= 1;
                        if let Some((o_sym, _)) = self.sta.pop() {
                            if let Some(sym) = o_sym {
                                //reduced_sym.push(sym.sym.clone());
                                reduced.push(sym);
                            } else {
                                return Err(DFAError::StackNoSymbol);
                            }
                        } else {
                            return Err(DFAError::StackEmpty);
                        }
                    }
                    let ret_sym = &prod.ret_sym;

                    // GOTO[top,<symbol>]
                    let top = self.sta.last().ok_or(DFAError::StackEmpty)?;
                    //println!("GOTO[{},{:?}] by prod_id = {}", top.1, ret_sym, p);
                    let next = get_goto(&top.1, &ret_sym)?;

                    self.state = next;
                    // 因为是栈，所以要逆序处理
                    reduced.reverse();
                    self.sta.push((
                        Some(ASTLink {
                            sym: Symbol::NonTerm(ret_sym.clone()),
                            adj: reduced,
                            index: idx,
                            prod_id: Some(p),
                            pd: None,
                            parser_ok: false,
                        }),
                        next,
                    ));

                    Ok(DFAOutput { action: action })
                }
                Action::Accept => {
                    self.is_ac = true;

                    Ok(DFAOutput { action: action })
                }
            },
            Err(e) => Err(e),
        }
    }
}

#[derive(Debug, Clone)]
pub struct ASTLink {
    pub sym: Symbol,
    pub index: usize,
    pub prod_id: Option<u32>, // 告诉 Parser 按什么式子归约解析
    pub parser_ok: bool,      // Parser 是否检查成功
    pub pd: Option<PD>,

    pub adj: Vec<ASTLink>,
}

// 动作类型
#[derive(Debug, Clone, PartialEq)]
pub enum Action {
    Shift(u32),  // 移进到指定状态
    Reduce(u32), // 按指定产生式规约
    Accept,      // 接受输入
}

#[derive(Debug, Clone, PartialEq)]
pub enum Symbol {
    Term(Token),
    NonTerm(NonTerm),
}

// 非终结符类型
#[derive(Debug, Clone, PartialEq)]
pub enum NonTerm {
    Program,
    Function,
    Statements,
    Statement,
    Exp,
    Term,
    Factor,
}

pub fn get_goto(s: &u32, nt: &NonTerm) -> Result<u32, DFAError> {
    match (s, nt) {
        (0, NonTerm::Function) => Ok(7),
        (0, NonTerm::Program) => Ok(1),
        (6, NonTerm::Statement) => Ok(8),

        (10, NonTerm::Exp) => Ok(11),
        (10, NonTerm::Term) => Ok(14),
        (10, NonTerm::Factor) => Ok(15),

        (13, NonTerm::Term) => Ok(24),
        (13, NonTerm::Factor) => Ok(15),

        (16, NonTerm::Factor) => Ok(17),
        (19, NonTerm::Factor) => Ok(20),

        (21, NonTerm::Exp) => Ok(22),
        (21, NonTerm::Term) => Ok(14),
        (21, NonTerm::Factor) => Ok(15),

        _ => Err(DFAError::NoGoto),
    }
}

pub fn get_action(s: &u32, t: &Token) -> Result<Action, DFAError> {
    // 无视条件，如果匹配则提前返回
    match s {
        7 => return Ok(Action::Reduce(0)),
        9 => return Ok(Action::Reduce(1)),
        12 => return Ok(Action::Reduce(2)),
        15 => return Ok(Action::Reduce(5)),
        23 => return Ok(Action::Reduce(9)),
        _ => {}
    };

    // 按 Token 判断
    match t {
        Token::Keyword(kw) => {
            if is_data_type(kw) {
                match s {
                    0 => Ok(Action::Shift(2)),
                    _ => Err(DFAError::NoAction),
                }
            } else if kw == "return" {
                match s {
                    6 => Ok(Action::Shift(10)),
                    _ => Err(DFAError::NoAction),
                }
            } else {
                Err(DFAError::NoAction)
            }
        }
        Token::UIntLiteral(_) => match s {
            10 | 13 | 16 | 19 | 21 => Ok(Action::Shift(18)),
            _ => Err(DFAError::NoAction),
        },
        Token::Brace(brace_type) => match (s, brace_type) {
            (3, BraceType::OpenRound) => Ok(Action::Shift(4)),
            (4, BraceType::CloseRound) => Ok(Action::Shift(5)),
            (5, BraceType::OpenCurly) => Ok(Action::Shift(6)),
            (8, BraceType::CloseCurly) => Ok(Action::Shift(9)),
            (10 | 13 | 16 | 19 | 21, BraceType::OpenRound) => Ok(Action::Shift(21)),

            (14, BraceType::CloseRound) => Ok(Action::Reduce(3)),
            (17, BraceType::CloseRound) => Ok(Action::Reduce(6)),
            (18, BraceType::CloseRound) => Ok(Action::Reduce(7)),
            (20, BraceType::CloseRound) => Ok(Action::Reduce(8)),
            (24, BraceType::CloseRound) => Ok(Action::Reduce(4)),
            (22, BraceType::CloseRound) => Ok(Action::Shift(23)),
            _ => Err(DFAError::NoAction),
        },
        Token::Semicolon => match s {
            11 => Ok(Action::Shift(12)),
            14 => Ok(Action::Reduce(3)),
            17 => Ok(Action::Reduce(6)),
            18 => Ok(Action::Reduce(7)),
            20 => Ok(Action::Reduce(8)),
            24 => Ok(Action::Reduce(4)),
            _ => Err(DFAError::NoAction),
        },
        Token::Identifier(_) => match s {
            2 => Ok(Action::Shift(3)),
            _ => Err(DFAError::NoAction),
        },
        Token::Eof => match s {
            1 => Ok(Action::Accept),
            _ => Err(DFAError::NoAction),
        },
        Token::Operation(op) => match (s, op) {
            (
                10 | 13 | 16 | 19 | 21,
                OpType::Negation | OpType::LogicalNegation | OpType::BitwiseComplement,
            ) => Ok(Action::Shift(19)),
            (11 | 22, OpType::Add | OpType::Negation) => Ok(Action::Shift(13)),
            (14, OpType::Add | OpType::Negation) => Ok(Action::Reduce(3)),
            (14 | 24, OpType::Mul | OpType::Div) => Ok(Action::Shift(16)),
            (17, OpType::Add | OpType::Negation | OpType::Mul | OpType::Div) => {
                Ok(Action::Reduce(6))
            }
            (18, OpType::Add | OpType::Negation | OpType::Mul | OpType::Div) => {
                Ok(Action::Reduce(7))
            }
            (20, OpType::Add | OpType::Negation | OpType::Mul | OpType::Div) => {
                Ok(Action::Reduce(8))
            }
            (24, OpType::Add | OpType::Negation) => Ok(Action::Reduce(4)),
            _ => Err(DFAError::NoAction),
        },
        Token::Unknown(_) => Err(DFAError::NoAction),
    }
}
